#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    char ch[4] = { 'A','C','G','T' };
    int bfs(string startGene, string endGene, unordered_map<string, int>& mp)
    {
        if (!mp[endGene])return -1;
        unordered_map<string, bool> st;
        queue<string> q;
        q.push(startGene);
        int ans = 0;

        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                string str = q.front();
                q.pop();

                if (str == endGene)return ans;
                for (int j = 0; j < str.size(); j++) {
                    for (int z = 0; z < 4; z++) {
                        char u = str[j];
                        str[j] = ch[z];
                        if (mp[str] && !st[str]) {
                            q.push(str);
                            st[str] = true;
                        }
                        str[j] = u;
                    }
                }
            }
            ans++;
        }
        return -1;

    }
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_map<string, int> mp;
        int n = bank.size();
        for (int i = 0; i < n; i++)mp[bank[i]]++;
        return bfs(startGene, endGene, mp);
    }
};